#pragma once

template<class T>
struct ListNode {
	T _data;
	ListNode* _next;
	ListNode* _prev;

	ListNode(const T& x = T()):_data(x),_next(nullptr),_prev(nullptr){}
};

template<class T>
struct list_iterator {
	typedef ListNode<T> node;
	typedef list_iterator self;
	node* _node;

	list_iterator(node* node):_node(node){}

	T& operator*() {
		return _node->_data;
	}

	self& operator++() {
		_node = _node->_next;
		return *this;
	}
	bool operator!=(const self& s) {
		return _node != s._node;
	}

};

template<class T>
class List {
public:
	typedef ListNode<T> node;
	typedef list_iterator<T> iterator;

	List(){
		empty_init();
	}

	iterator begin() {
		return _head->_next;
	}
	iterator end() {
		return _head;
	}

	void empty_init() {
		_head = new node;
		_head->_prev = _head;
		_head->_next = _head;
	}

	void push_back(const node& x) {
		node* prev = _head->_prev;
		node* newnode = new node(x);

		prev->_next = newnode;
		newnode->_prev = prev;

		_head->_prev = newnode;
		newnode->_next = _head;
	}

private:
	node* _head;
};
